{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Largest Value in Each Tree Row"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestValues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在每个树行中找最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉树的根节点&nbsp;<code>root</code> ，请找出该二叉树中每一层的最大值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/21/largest_e1.jpg\" style=\"height: 172px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [1,3,2,5,3,null,9]\n",
    "<strong>输出: </strong>[1,3,9]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [1,2,3]\n",
    "<strong>输出: </strong>[1,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[0,10<sup>4</sup>]</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>-2<sup>31</sup>&nbsp;&lt;= Node.val &lt;= 2<sup>31</sup>&nbsp;- 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-largest-value-in-each-tree-row](https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-largest-value-in-each-tree-row](https://leetcode.cn/problems/find-largest-value-in-each-tree-row/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,5,3,null,9]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        largests = []\n",
    "        queue = collections.deque([root])\n",
    "\n",
    "        while queue:\n",
    "            maxi = queue[0].val\n",
    "            size = len(queue)\n",
    "\n",
    "            for _ in range(size):\n",
    "                maxi = max(queue[0].val, maxi)\n",
    "\n",
    "                if queue[0].left:\n",
    "                    queue.append(queue[0].left)\n",
    "                if queue[0].right:\n",
    "                    queue.append(queue[0].right)\n",
    "                \n",
    "                queue.popleft()\n",
    "            \n",
    "            largests.append(maxi)\n",
    "\n",
    "        return largests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ans, stack = [], [root] if root else []\n",
    "        while stack:\n",
    "            temp, cur = [], float(\"-inf\")\n",
    "            for s in stack:\n",
    "                cur = max(s.val, cur)\n",
    "                if s.left:\n",
    "                    temp.append(s.left)\n",
    "                if s.right:\n",
    "                    temp.append(s.right)\n",
    "            stack[:] = temp\n",
    "            ans.append(cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        l = []\n",
    "        if not root:\n",
    "            return l\n",
    "        q = []\n",
    "        q.append(root)\n",
    "        m = 0\n",
    "        while len(q)!=0:\n",
    "            size = len(q)\n",
    "            m = q[0].val\n",
    "            while size>0:\n",
    "                tem = q.pop(0)\n",
    "                if tem.val>m: m = tem.val\n",
    "                if tem.left!=None: q.append(tem.left)\n",
    "                if tem.right!=None: q.append(tem.right)    \n",
    "                size-=1\n",
    "            l.append(m)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=515 lang=python3\n",
    "#\n",
    "# [515] 在每个树行中找最大值\n",
    "#\n",
    "# https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/description/\n",
    "#\n",
    "# algorithms\n",
    "# Medium (54.95%)\n",
    "# Total Accepted:    1.8K\n",
    "# Total Submissions: 3.2K\n",
    "# Testcase Example:  '[1,3,2,5,3,null,9]'\n",
    "#\n",
    "# 您需要在二叉树的每一行中找到最大的值。\n",
    "# \n",
    "# 示例：\n",
    "# \n",
    "# \n",
    "# 输入: \n",
    "# \n",
    "# ⁠         1\n",
    "# ⁠        / \\\n",
    "# ⁠       3   2\n",
    "# ⁠      / \\   \\  \n",
    "# ⁠     5   3   9 \n",
    "# \n",
    "# 输出: [1, 3, 9]\n",
    "# \n",
    "# \n",
    "#\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def largestValues(self, root: 'TreeNode') -> 'List[int]':\n",
    "        q = Queue()\n",
    "        if root is None: return []\n",
    "        q.put((root, 0))\n",
    "        res = []\n",
    "        maxx = 0\n",
    "        while not q.empty():\n",
    "            p, h = q.get()\n",
    "            maxx = max(maxx, h)\n",
    "            if h >= len(res):\n",
    "                res.append(p.val)\n",
    "            else:\n",
    "                res[h] = max(res[h], p.val)\n",
    "            if p.left: q.put((p.left, h+1))\n",
    "            if p.right: q.put((p.right, h+1))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "        while len(stack):\n",
    "            lens = len(stack)\n",
    "            bigger = -11111111111111\n",
    "            for i in range(lens):\n",
    "                cur = stack.pop(0)\n",
    "                if cur.val > bigger:\n",
    "                    bigger = cur.val\n",
    "                if cur.left:\n",
    "                    stack.append(cur.left)\n",
    "                if cur.right:\n",
    "                    stack.append(cur.right)\n",
    "            res.append(bigger)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        tree_dict = {}\n",
    "        def pre_order(node,i=1):\n",
    "            if node != None:\n",
    "                if i in tree_dict:\n",
    "                    tree_dict[i].append(node.val)\n",
    "                else:\n",
    "                    tree_dict[i] = [node.val]\n",
    "                i+=1\n",
    "                pre_order(node.left,i)\n",
    "                pre_order(node.right,i)\n",
    "        pre_order(root)\n",
    "        result = [value for value in tree_dict.values()]\n",
    "        return [max(value) for value in result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        res = []\n",
    "        def inner(node, depth=1):\n",
    "            if not node:\n",
    "                return\n",
    "            if len(res) < depth:\n",
    "                res.append(node.val)\n",
    "            else:\n",
    "                res[depth-1] = max(res[depth-1], node.val)\n",
    "            inner(node.left,depth+1)\n",
    "            inner(node.right,depth+1)\n",
    "        inner(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return \n",
    "        stack = [root]\n",
    "        result = []\n",
    "        while stack:\n",
    "            max_now = float('-inf')\n",
    "            n = len(stack)\n",
    "            for _ in range(n):\n",
    "                node = stack.pop(0)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                max_now = max(max_now, node.val)\n",
    "            result.append(max_now)\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        self.ans=[]\n",
    "        def BiBFS(root):\n",
    "            \"\"\"\n",
    "            type root: TreeNode\n",
    "            \"\"\"\n",
    "            if not root:\n",
    "                return\n",
    "            my_queue = collections.deque()\n",
    "            node = root\n",
    "            my_queue.append(node)\n",
    "            while my_queue:\n",
    "                level_len = len(my_queue)\n",
    "                maxval=float('-inf')\n",
    "                for i in range(level_len):\n",
    "                    node = my_queue.popleft()\n",
    "                    maxval=max(maxval,node.val)\n",
    "                    if node.left:\n",
    "                        my_queue.append(node.left)\n",
    "                    if node.right:\n",
    "                        my_queue.append(node.right)\n",
    "                self.ans.append(maxval)\n",
    "        BiBFS(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        row = [root]\n",
    "        while row:\n",
    "            ans.append(max(node.val for node in row))\n",
    "            row = [child for node in row for child in (node.left, node.right) if child]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        res =[]\n",
    "        if not root:return res\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            tmp = float('-inf')\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                tmp=max(tmp,cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return\n",
    "\n",
    "        res = []\n",
    "        q = collections.deque([root])\n",
    "\n",
    "        while q:\n",
    "            val = None\n",
    "            for _ in range(len(q)):\n",
    "                curr = q.popleft()\n",
    "                if val is None or curr.val > val:\n",
    "                    val = curr.val\n",
    "                if curr.left: q.append(curr.left)\n",
    "                if curr.right: q.append(curr.right)\n",
    "            res.append(val)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            layer = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                layer.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(max(layer))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# BFS\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "        \n",
    "        res = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            level = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                level.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(max(level))\n",
    "            \n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#from collections impport deque\n",
    "#from collections impport defaultdict\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return None\n",
    "        max_val = []\n",
    "        def dfs(root,depth):\n",
    "            nonlocal max_val\n",
    "            if not root:\n",
    "                return\n",
    "            if depth > len(max_val)-1:\n",
    "                max_val.append(root.val)\n",
    "            else:\n",
    "                max_val[depth] = max(max_val[depth],root.val)\n",
    "            \n",
    "            if root.left:\n",
    "                dfs(root.left,depth+1)\n",
    "            if root.right:\n",
    "                dfs(root.right,depth+1)\n",
    "        \n",
    "        dfs(root,0)\n",
    "\n",
    "        return max_val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        # 深搜，回溯法，用一个depth来记录层数\n",
    "        # 广搜，直接层次遍历\n",
    "\n",
    "        res = []\n",
    "        depth = 0\n",
    "\n",
    "        def dfs(node, depth):\n",
    "            if not node:\n",
    "                return\n",
    "            if depth < len(res):\n",
    "                res[depth] = max(res[depth], node.val)\n",
    "            else:\n",
    "                res.append(node.val)\n",
    "\n",
    "            depth += 1\n",
    "            dfs(node.left, depth)\n",
    "            dfs(node.right, depth)\n",
    "            depth -= 1      # 回溯\n",
    "        \n",
    "        dfs(root, depth)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        queue = deque()\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            m = float('-inf')\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                m = max(m, node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(m)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        node_list = [root]\n",
    "        res = []\n",
    "        while node_list:\n",
    "            child_list = []\n",
    "            row_list = []\n",
    "            for node in node_list:\n",
    "                if not row_list:\n",
    "                    row_list.append(node.val)\n",
    "                elif node.val > row_list[-1]:\n",
    "                    row_list.append(node.val)\n",
    "                if node.left:\n",
    "                    child_list.append(node.left)\n",
    "                if node.right:\n",
    "                    child_list.append(node.right)\n",
    "            node_list = child_list\n",
    "            res.append(row_list[-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        s=[root]\n",
    "        s1=[]\n",
    "        list1=[]\n",
    "        if root == None:\n",
    "            return []\n",
    "        while len(s)!=0:\n",
    "            s2=[]\n",
    "            s3=[]\n",
    "            \n",
    "            \n",
    "            for i in range(len(s)):\n",
    "                p=s.pop()\n",
    "                s3.append(p.val)\n",
    "                if p.left!=None:\n",
    "                    s2.append(p.left)\n",
    "                if p.right!=None:\n",
    "                    s2.append(p.right)\n",
    "            s=s2\n",
    "            s1.append(s3)\n",
    "        \n",
    "        for i in s1:\n",
    "            a=max(i)\n",
    "            list1.append(a)\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        \n",
    "        res=[]\n",
    "        from collections import deque\n",
    "        q=deque([root])\n",
    "\n",
    "        while q:\n",
    "            val=[] # 存储每一层的val\n",
    "            l=len(q)\n",
    "            for _ in range(l):\n",
    "                node=q.popleft()\n",
    "                val.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            res.append(val)\n",
    "        \n",
    "        return [max(l) for l in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[float]:\n",
    "        from collections import deque\n",
    "        # 按照102.层序遍历来计算，得到每层最大值\n",
    "        que = deque([root])\n",
    "\n",
    "        final_result = []\n",
    "        if not root: return final_result\n",
    "\n",
    "        while que:\n",
    "            n = len(que)\n",
    "            result = []\n",
    "            # 遍历当前层的同时，加入下一层的节点\n",
    "            for _ in range(n):\n",
    "                cur = que.popleft()\n",
    "                result.append(cur.val)\n",
    "\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "            final_result.append(max(result))\n",
    "        return final_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        tmp = float('-inf')\n",
    "        \n",
    "        que = deque([root])\n",
    "        last = root\n",
    "        new_last = root\n",
    "\n",
    "        while que:\n",
    "            node = que.popleft()\n",
    "            if node.left:\n",
    "                que.append(node.left)\n",
    "                new_last = node.left\n",
    "            if node.right:\n",
    "                que.append(node.right)\n",
    "                new_last = node.right\n",
    "            if node.val > tmp:\n",
    "                tmp = node.val\n",
    "\n",
    "            if node == last:\n",
    "                res.append(tmp)\n",
    "                tmp = float('-inf')\n",
    "                last = new_last\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "\r\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\r\n",
    "        results = []\r\n",
    "        if not root:\r\n",
    "            return results\r\n",
    "        if root:\r\n",
    "            dqe = deque([root])\r\n",
    "        while dqe:\r\n",
    "            result = []\r\n",
    "            size = len(dqe)\r\n",
    "            for _ in range(size):\r\n",
    "                node = dqe.popleft()\r\n",
    "                result.append(node.val)\r\n",
    "                if node.left:\r\n",
    "                    dqe.append(node.left)\r\n",
    "                if node.right:\r\n",
    "                    dqe.append(node.right)\r\n",
    "            results.append(result)\r\n",
    "        final = []\r\n",
    "        for i in range(len(results)):\r\n",
    "            max_val = max(results[i])\r\n",
    "            final.append(max_val)\r\n",
    "\r\n",
    "        return final\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node: TreeNode, curHeight: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            if curHeight == len(ans):\n",
    "                ans.append(node.val)\n",
    "            else:\n",
    "                ans[curHeight] = max(ans[curHeight], node.val)\n",
    "            dfs(node.left, curHeight + 1)\n",
    "            dfs(node.right, curHeight + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = collections.deque([root])\n",
    "        result = []\n",
    "        while queue:\n",
    "            maxValue = float(\"-inf\")\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                maxValue = max(maxValue, node.val)\n",
    "                if  node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            result.append(maxValue)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        result = []\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                tmp.append(node.val)\n",
    "            result.append(max(tmp))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\r\n",
    "        result = []\r\n",
    "        if not root:\r\n",
    "            return result\r\n",
    "        queue = deque([root])\r\n",
    "        while queue:\r\n",
    "            maxN = -float(\"inf\")\r\n",
    "            for _ in range(len(queue)):\r\n",
    "                node = queue.popleft()\r\n",
    "                maxN = max(maxN, node.val)\r\n",
    "                if node.left:\r\n",
    "                    queue.append(node.left)\r\n",
    "                if node.right:\r\n",
    "                    queue.append(node.right)\r\n",
    "            result.append(maxN)\r\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def largestValues(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(root, curheight):\n",
    "            if not root:\n",
    "                return \n",
    "            if curheight == len(ans):\n",
    "                ans.append(root.val)\n",
    "            else:\n",
    "                ans[curheight] = max(ans[curheight], root.val)\n",
    "            dfs(root.left, curheight + 1)\n",
    "            dfs(root.right, curheight + 1)\n",
    "        dfs(root, 0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
